package interview;

import java.util.*;

public class lc347 {
    public static void main(String[] args) {
        int[] ans = topKFrequent(new int[]{1,1,2,2,3,3}, 2);
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i] + " ");
        }
    }
    public static int[] topKFrequent1(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        List<Map.Entry> list = new ArrayList<>(map.entrySet());
        Collections.sort(list,(a, b) -> {
            return (int)b.getValue() - (int)a.getValue();
        });
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = (int)list.get(i).getKey();
        }
        return ans;
    }

    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<Map.Entry> queue = new PriorityQueue<>((a, b) ->{
            return (int)a.getValue() - (int)b.getValue();
        });
        for (Map.Entry entry : map.entrySet()) {
            if(queue.size() == k){
                if((int)entry.getValue() > (int)queue.peek().getValue()){
                    queue.poll();
                    queue.offer(entry);
                }
            }
            else
                queue.offer(entry);
        }
        int[] ans = new int[k];
        int i = 0;
        for (Map.Entry entry : queue){
            ans[i++] = (int)entry.getKey();
        }
        return ans;
    }

}
